package com.sam.mooc;

import java.util.Arrays;

/**
 * 二分查找
 * Created by samwang on 2017/12/10.
 */
public class BirarySeach {
    public static void main(String[] args) {
        int[] a = {1, 2, 3, 4, 5, 6, 7, 8};

        System.out.println(getFx());
        System.out.println(fx(getFx()));

    }

    public static int search(int[] a, int target) {//时间复杂度 O（logn）
        int right = a.length - 1;
        int left = 0;
        int mid;
        while (left <= right) {
            mid = left + (right - left) / 2;//二分中间数的index;防止l+r溢出
            if (a[mid] == target) {
                return mid;
            } else if (a[mid] > target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }

        }

        return -1;
    }

    /**
     * 查找比t小的下标最大的原素。
     * @param a
     * @param target
     * @return
     */
    public static int lowerBound(int[] a, int target) {
        int lastPos = -1;
        int l = 0;
        int r = a.length;
        int mid;
        while (l <= r) {
            mid = l + (r - l) / 2;
            if (a[mid] < target) {
                lastPos = mid;
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }

        return lastPos;
    }

    /**
     * ---------------------
     * 二分法求方程的根
     * f(x)=x^3-5x^2+10x-10=0
     * f（x）单调递增，f(0)<0;
     * f(100)>0 故0,100有且只有一个解
     * @return
     */
    public static double getFx() {
        double l = 0;
        double r = 100;
        double mid;
        double fx;
        final double t = 1e-6;
        while (l < r) {
            mid = l + (r - l) / 2;
            fx = fx(mid);
            if (Math.abs(fx) <= t) {
                return mid;
            } else if (fx > 0) {
                r = mid;
            } else {
                l = mid;
            }
        }
        return 0;
    }

    public static double fx(double x) {
        return Math.pow(x, 3) - 5 * Math.pow(x, 2) +10 * x - 80;
    }

    //------end 解方程的根


    /**
     * 找出两个数和为t,a的长度<=100,000
     */
    public static void searchTwoSumT(int[] a, int t) {
        // 双重遍历O(n^2)，100亿算法过不了
        // a[i]+a[j] = t

        //算法2 O(nlog(n))
        //快速排序O(nlog(n))+ a[i],二分查找 O(nlog(n))

        Arrays.sort(a);
        for(int i=0;i<a.length;i++) {
            int l = 0;
            int r = a.length;
            int temp = t - a[i];
            int mid;
            while (l < r) {
                mid = l + (r - l) / 2;
                if (a[mid] == temp) {
                    System.out.println(i + "," + mid);
                    return;
                } else if (a[mid] < temp) {
                    r = mid - 1;
                } else {
                    l = mid + 1;
                }

            }
        }

        //方法3，排序完，从两边同时取i,j ;a[i]+a[j]与t比较，小了i++;大了j--
//        int i = 0;
//        int j = a.length;
//        int temp = a[i] + a[j];
//        while (temp != t) {
//            if (temp > t) {
//                j--;
//            } else {
//                i++;
//            }
//        }
//        System.out.println(i + "," + j);

    }


}
